Trước năm 1978, đảo Phan Vinh có tên là Hòn Sập. Đầu năm 1978, tình hình ở khu vực quần đảo Trường Sa diễn biến phức tạp, Philippines đưa quân chiếm đóng bãi An Nhơn (tên cũ là cồn san hô Lan Can), một số nước đưa nhiều tàu thuyền đến khu vực quần đảo Trường Sa. Quân chủng Hải quân Việt Nam quyết định phải nhanh chóng tổ chức lực lượng đóng giữ các đảo Trường Sa Đông, Sinh Tồn Đông, Hòn Sập, An Bang.

Ngày 30/3/1978, một phân đội gồm 31 người của Trung đoàn 146, Vùng 4 Hải quân do Thiếu úy Vũ Xuân Hà chỉ huy, có Trung đoàn trưởng Cao Ánh Đăng đi cùng trên tàu 680 thuộc Đoàn 128 đã ra đóng giữ đảo Hòn Sập (tức đảo Phan Vinh).

Tên của đảo xuất phát từ tên của Anh hùng lực lượng vũ trang nhân dân, Trung úy Nguyễn Phan Vinh (1933–1968, quê ở Điện Bàn, Quảng Nam), vốn là thuyền trưởng của nhiều con tàu không số trong Chiến tranh Việt Nam.